// Package _24__二叉树中的最大路径和 main
// @Title _24__二叉树中的最大路径和
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-03-03 10:16
// @Create  2022-03-03 10:16
package main

import "math"

//Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 这他妈是一个动态规划的问题  树形DP
func maxPathSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var ans = math.MinInt32
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		// 递归求左右子树的最大和
		leftSonTree := max(dfs(node.Left), 0)
		rightSonTree := max(dfs(node.Right), 0)
		// 最大路径为
		maxPath := node.Val + leftSonTree + rightSonTree
		ans = max(ans, maxPath)
		return node.Val + max(leftSonTree, rightSonTree)
	}
	dfs(root)
	return ans
}

func main() {

}
